package com.lzq.leetcode.templates;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class s739_ST {

    public static int[] dailyTemperatures(int[] temperatures) {

        Deque<Integer> stack = new LinkedList<>();
        int n = temperatures.length;
        int[] ret = new int[n];

        for (int i=n-1; i>=0; i--) {
            while (!stack.isEmpty() && temperatures[stack.peek()]<=temperatures[i]) {
                stack.pop();
            }
            ret[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
            stack.push(i);
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] temperatures = new int[]{73,74,75,71,69,72,76,73};
        int[] ret = dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(ret));
    }

    /*
    public static int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();

        int len = temperatures.length;
        int[] ret = new int[len];
        for (int i=len-1; i>=0; i--) {
            while ( (!stack.isEmpty()) && temperatures[stack.peek()] < temperatures[i]) {
                stack.pop();
            }
            if (!stack.isEmpty())   {
                ret[i] = stack.peek() - i;
            } else {
                ret[i] = 0;
            }

            stack.push(i);
        }
        return ret;
    }
    */
}
